package javaCode.chapter06.练习;

public class MiGong {

    public static void main(String[] args) {

        //思路
        //1. 先创建迷宫，用二维数组表示 int[][]
        //2. 先规定 map 数组的元素值：0表示可以走的路，1表示障碍物

        int [][] map = new int[8][7];
        //3. 将最上面的一行和最下面的一行，全部设置为1
        for (int i = 0; i < map[i].length; i++) {
            map[0][i]=1;
            map[map[i].length][i]=1;
        }
        //4. 将最右的一列和最左的一列，全部设置为1
        for (int i = 0; i < map.length; i++) {
            map[i][0]=1;
            map[i][map[i].length-1]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        map[2][2]=1;
        //map[2][1]=1;
        //map[1][2]=1;

        //输出当前的地图
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }

        //使用 findWay给老鼠找路
        TB tb1 = new TB();
        tb1.findWay(map,1,1);

        System.out.println("===找路的情况如下====");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
    }
}

class TB {

    // 使用递归回溯的思想来解决老实出迷宫
    // 题意解读
    //1. findWay方法就是专门来找出迷宫的路径
    //2. 如果找到，就返回 true，否则返回 false
    //3. map 就是二维数组，即表示迷宫
    //4. i,j 就是老师的位置，初始化的位置为(1,1)
    //5. 因为我们是递归的找路，所以我先规定 map数组的各个值的含义
    //   0 表示可以走  1表示障碍物  2表示可以走  3表示走过，但是走不通是死路
    //6. 当map[6][5] = 2 就说明找到通路，就可以结束，否则就继续找。
    //7. 先确定老师找路策略 下->右->上->左
    public boolean findWay(int[][] map,int i,int j){

        if (map[6][5]==2){ //说明已经找到
            return true;
        }else{
            if (map[i][j]==0){ //当前这个位置0，说明表示可以走
            //我们假定可以走通
                map[i][j]=2;
                //使用找路策略，来确定该位置是否真的可以走通
                //下->右->上->左
                if (findWay(map,i+1,j)){ //先往下
                    return true;
                }else if (findWay(map,i,j+1)){ //右
                    return true;
                }else if (findWay(map,i-1,j)){ //上
                    return true;
                }else if (findWay(map,i,j-1)){ //左
                    return true;
                }else {
                    map[i][j] =3;
                    return false;
                }

            }else { // map[i][j] = 1,2,3
                return false;
            }
        }
    }


    //修改策略，看看路径是否有变化
    //下->右->上->左 ==> 上->右->下->左
    public boolean findWay2(int[][] map,int i,int j) {

        if (map[6][5] == 2) { //说明已经找到
            return true;
        } else {
            if (map[i][j] == 0) { //当前这个位置0，说明表示可以走
                //我们假定可以走通
                map[i][j] = 2;
                //使用找路策略，来确定该位置是否真的可以走通
                //下->右->上->左
                if (findWay2(map, i - 1, j)) { //先往上
                    return true;
                } else if (findWay2(map, i, j + 1)) { //右
                    return true;
                } else if (findWay2(map, i + 1, j)) { //下
                    return true;
                } else if (findWay2(map, i, j - 1)) { //左
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }

            } else { // map[i][j] = 1,2,3
                return false;
            }
        }
    }

}


